<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
    

    

    



    <meta charset="utf-8">
    
    
    <meta name="sogou_site_verification" content="true">
    
    
    
    <title>【算法】10亿int型数，统计只出现一次的数 | Lvshen&#39;s Blog | This is My World</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="算法,bitmap">
    <meta name="baidu-site-verification" content="VIVNdSiMZm">
    <meta name="description" content="本文来自 Itimetraveler’s Blog： 【算法】10亿int型数，统计只出现一次的数  题目10亿int整型数，以及一台可用内存为1GB的机器，时间复杂度要求O(n)，统计只出现一次的数？ 分析首先分析多大的内存能够表示10亿的数呢？一个int型占4字节，10亿就是40亿字节（很明显就是4GB），也就是如果完全读入内存需要占用4GB，而题目只给1GB内存，显然不可能将所有数据读入内">
<meta name="keywords" content="算法,bitmap">
<meta property="og:type" content="article">
<meta property="og:title" content="【算法】10亿int型数，统计只出现一次的数">
<meta property="og:url" content="https://lvshen9.gitee.io/2017/08/27/bitmap/index.html">
<meta property="og:site_name" content="Lvshen&#39;s Blog">
<meta property="og:description" content="本文来自 Itimetraveler’s Blog： 【算法】10亿int型数，统计只出现一次的数  题目10亿int整型数，以及一台可用内存为1GB的机器，时间复杂度要求O(n)，统计只出现一次的数？ 分析首先分析多大的内存能够表示10亿的数呢？一个int型占4字节，10亿就是40亿字节（很明显就是4GB），也就是如果完全读入内存需要占用4GB，而题目只给1GB内存，显然不可能将所有数据读入内">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://itimetraveler.github.io/gallery/bitmap/37237-20160302211041080-958649492.png">
<meta property="og:image" content="https://itimetraveler.github.io/gallery/bitmap/37237-20160302215109220-1394239868.png">
<meta property="og:updated_time" content="2017-08-27T08:16:31.401Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="【算法】10亿int型数，统计只出现一次的数">
<meta name="twitter:description" content="本文来自 Itimetraveler’s Blog： 【算法】10亿int型数，统计只出现一次的数  题目10亿int整型数，以及一台可用内存为1GB的机器，时间复杂度要求O(n)，统计只出现一次的数？ 分析首先分析多大的内存能够表示10亿的数呢？一个int型占4字节，10亿就是40亿字节（很明显就是4GB），也就是如果完全读入内存需要占用4GB，而题目只给1GB内存，显然不可能将所有数据读入内">
<meta name="twitter:image" content="https://itimetraveler.github.io/gallery/bitmap/37237-20160302211041080-958649492.png">
    
    <link rel="shortcut icon" href="/img/mylogo.jpg">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

</head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/img/brand.jpg)">
      <div class="brand">
        <a href="/" class="avatar waves-effect waves-circle waves-light">
          <img src="/img/avatar.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">我的技术小房间</h5>
          <a href="mailto:https://lvshen9.github.io" title="https://lvshen9.github.io" class="mail">https://lvshen9.github.io</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/"  >
                <i class="icon icon-lg icon-home"></i>
                主页
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                Archives
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                Tags
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/categories"  >
                <i class="icon icon-lg icon-th-list"></i>
                Categories
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/about"  >
                <i class="icon icon-lg icon-address-book"></i>
                About
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/collection"  >
                <i class="icon icon-lg icon-apple"></i>
                Collection
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://lvshen9.github.io/" target="_blank" >
                <i class="icon icon-lg icon-wordpress"></i>
                Blog
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/lvshen9" target="_blank" >
                <i class="icon icon-lg icon-github-alt"></i>
                GitHub
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">【算法】10亿int型数，统计只出现一次的数</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="输入感兴趣的关键字">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">【算法】10亿int型数，统计只出现一次的数</h1>
        <h5 class="subtitle">
            
                <time datetime="2017-08-27T07:52:21.000Z" itemprop="datePublished" class="page-time">
  2017-08-27
</time>


	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/技术/">技术</a></li></ul>

            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#题目"><span class="post-toc-number">1.</span> <span class="post-toc-text">题目</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#分析"><span class="post-toc-number">2.</span> <span class="post-toc-text">分析</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#1、位图法（Bitmap）"><span class="post-toc-number">2.1.</span> <span class="post-toc-text">1、位图法（Bitmap）</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#具体方案"><span class="post-toc-number">2.1.1.</span> <span class="post-toc-text">具体方案</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#Bitmap拓展"><span class="post-toc-number">2.1.2.</span> <span class="post-toc-text">Bitmap拓展</span></a></li></ol></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#2、分治法"><span class="post-toc-number">2.2.</span> <span class="post-toc-text">2、分治法</span></a></li></ol></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#参考资料"><span class="post-toc-number">3.</span> <span class="post-toc-text">参考资料</span></a></li></ol>
        </nav>
    </aside>


<article id="post-bitmap"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">【算法】10亿int型数，统计只出现一次的数</h1>
        <div class="post-meta">
            <time class="post-time" title="2017-08-27 15:52:21" datetime="2017-08-27T07:52:21.000Z"  itemprop="datePublished">2017-08-27</time>

            
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/技术/">技术</a></li></ul>



            
<span id="busuanzi_container_page_pv" title="文章总阅读量" style='display:none'>
    <i class="icon icon-eye icon-pr"></i><span id="busuanzi_value_page_pv"></span>
</span>


        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <blockquote>
<p>本文来自 Itimetraveler’s Blog： <a href="https://itimetraveler.github.io/2017/07/13/%E3%80%90%E7%AE%97%E6%B3%95%E3%80%9110%E4%BA%BFint%E5%9E%8B%E6%95%B0%EF%BC%8C%E7%BB%9F%E8%AE%A1%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E6%95%B0/" target="_blank" rel="noopener">【算法】10亿int型数，统计只出现一次的数</a></p>
</blockquote>
<h2 id="题目"><a href="#题目" class="headerlink" title="题目"></a><strong>题目</strong></h2><p>10亿int整型数，以及一台可用内存为1GB的机器，时间复杂度要求O(n)，统计只出现一次的数？</p>
<h2 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h2><p>首先分析多大的内存能够表示10亿的数呢？一个int型占4字节，10亿就是40亿字节（很明显就是4GB），也就是如果完全读入内存需要占用4GB，而题目只给1GB内存，显然不可能将所有数据读入内存。</p>
<p>我们先不考虑时间复杂度，仅考虑解决问题。那么接下来的思路一般有两种。</p>
<ol>
<li><p><strong>位图法</strong>：用一个bit位来标识一个int整数。</p>
</li>
<li><p><strong>分治法</strong>：分批处理这10亿的数。</p>
<a id="more"></a>
</li>
</ol>
<p>一种是位图法，如果各位老司机有经验的话很快会想到int整型数是4字节（Byte），也就是32位（bit），如果能用一个bit位来标识一个int整数那么存储空间将大大减少。另一种是分治法，内存有限，我想办法分批读取处理。下面大致分析一下两种思路。</p>
<h3 id="1、位图法（Bitmap）"><a href="#1、位图法（Bitmap）" class="headerlink" title="1、位图法（Bitmap）"></a>1、位图法（Bitmap）</h3><p>位图法是基于int型数的表示范围这个概念的，用一个bit位来标识一个int整数，若该位为1，则说明该数出现；若该位为0，则说明该数没有出现。一个int整型数占4字节（Byte），也就是32位（bit）。那么把所有int整型数字表示出来需要2^32 bit的空间，换算成字节单位也就是2^32/8 = 2^29 Byte，大约等于512MB</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 插播一个常识</span></span><br><span class="line"><span class="number">2</span>^<span class="number">10</span> Byte = <span class="number">1024</span> Byte = <span class="number">1</span>KB</span><br><span class="line"><span class="number">2</span>^<span class="number">30</span> Byte = (<span class="number">2</span>^<span class="number">10</span>)^<span class="number">3</span> Byte = <span class="number">1024</span> * <span class="number">1024</span> * <span class="number">1024</span> Byte = <span class="number">1</span>GB</span><br></pre></td></tr></table></figure>
<p>这下就好办了，只需要用512MB的内存就能存储所有的int的范围数。</p>
<h4 id="具体方案"><a href="#具体方案" class="headerlink" title="具体方案"></a>具体方案</h4><p>那么接下来我们只需要申请一个int数组长度为 int tmp[<strong>N/32+1</strong>]即可存储完这些数据，其中<strong>N代表要进行查找的总数（这里也就是2^32）</strong>，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:</p>
<ul>
<li>tmp[0]:可表示0~31</li>
<li>tmp[1]:可表示32~63</li>
<li>tmp[2]可表示64~95</li>
<li>~~</li>
</ul>
<p>假设这10亿int数据为：6,3,8,32,36,……，那么具体的BitMap表示为：</p>
<p>[<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="https://itimetraveler.github.io/gallery/bitmap/37237-20160302211041080-958649492.png" alt="img](https://itimetraveler.github.io/gallery/bitmap/37237-20160302211041080-958649492.png)" title>
                </div>
                <div class="image-caption">img](https://itimetraveler.github.io/gallery/bitmap/37237-20160302211041080-958649492.png)</div>
            </figure></p>
<p>(1). 如何判断int数字放在哪一个tmp数组中：将数字直接除以32取整数部分(x/32)，例如：整数8除以32取整等于0，那么8就在tmp[0]上；</p>
<p>(2). 如何确定数字放在32个位中的哪个位：将数字mod32取模(x%32)。上例中我们如何确定8在tmp[0]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp[0]中的第8 mod上32等于8，那么整数8就在tmp[0]中的第八个bit位（从右边数起）。</p>
<p>然后我们怎么统计只出现一次的数呢？每一个数出现的情况我们可以分为三种：0次、1次、大于1次。也就是说我们需要用2个bit位才能表示每个数的出现情况。此时则三种情况分别对应的bit位表示是：00、01、11</p>
<p>我们顺序扫描这10亿的数，在对应的双bit位上标记该数出现的次数。最后取出所有双bit位为01的int型数就可以了。</p>
<h4 id="Bitmap拓展"><a href="#Bitmap拓展" class="headerlink" title="Bitmap拓展"></a>Bitmap拓展</h4><p>位图（Bitmap）算法思想比较简单，但关键是如何确定十进制的数映射到二进制bit位的map图。</p>
<p><strong>优点：</strong></p>
<ol>
<li>运算效率高，不许进行比较和移位；</li>
<li>占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M</li>
</ol>
<p><strong>缺点：</strong>所有的数据不能重复。即不可对重复的数据进行排序和查找。</p>
<p>建立了Bit-Map之后，就可以方便的使用了。一般来说Bit-Map可作为数据的<strong>查找、去重、排序</strong>等操作。比如以下几个例子：</p>
<blockquote>
<p>1、在3亿个整数中找出重复的整数个数，限制内存不足以容纳3亿个整数</p>
</blockquote>
<p>对于这种场景可以采用2-BitMap来解决，即为每个整数分配2bit，用不同的0、1组合来标识特殊意思，如00表示此整数没有出现过，01表示出现一次，11表示出现过多次，就可以找出重复的整数了，其需要的内存空间是正常BitMap的2倍，为：3亿*2/8/1024/1024=71.5MB。</p>
<p><strong>具体的过程如下：</strong>扫描着3亿个整数，组BitMap，先查看BitMap中的对应位置，如果00则变成01，是01则变成11，是11则保持不变，当将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为11的整数输出即可。</p>
<blockquote>
<p>2、对没有重复元素的整数进行排序</p>
</blockquote>
<p>对于非重复的整数排序BitMap有着天然的优势，它只需要将给出的无重复整数扫描完毕，组装成为BitMap之后，那么直接遍历一遍Bit区域就可以达到排序效果了。</p>
<p>举个例子：对整数4、3、1、7、6进行排序：</p>
<p>[<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="https://itimetraveler.github.io/gallery/bitmap/37237-20160302215109220-1394239868.png" alt="img](https://itimetraveler.github.io/gallery/bitmap/37237-20160302215109220-1394239868.png)" title>
                </div>
                <div class="image-caption">img](https://itimetraveler.github.io/gallery/bitmap/37237-20160302215109220-1394239868.png)</div>
            </figure></p>
<p>直接按Bit位输出就可以得到排序结果了。</p>
<blockquote>
<p>3、已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数</p>
</blockquote>
<p>8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话。</p>
<blockquote>
<p>4、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数</p>
</blockquote>
<p>将bit-map扩展一下，用2bit表示一个数即可：0表示未出现；1表示出现一次；2表示出现2次及以上，即重复，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。</p>
<p>最后放一个使用Byte[]数组存储、读取bit位的示例代码，来自<a href="http://yacare.iteye.com/blog/1969931" target="_blank" rel="noopener">利用位映射原理对大数据排重</a>：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BitmapTest</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> CAPACITY = <span class="number">1000000000</span>;<span class="comment">//数据容量</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">// 定义一个byte数组缓存所有的数据</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">byte</span>[] dataBytes = <span class="keyword">new</span> <span class="keyword">byte</span>[<span class="number">1</span> &lt;&lt; <span class="number">29</span>];</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        BitmapTest ms = <span class="keyword">new</span> BitmapTest();</span><br><span class="line"></span><br><span class="line">        <span class="keyword">byte</span>[] bytes = <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">        Random random = <span class="keyword">new</span> Random();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; CAPACITY; i++) &#123;</span><br><span class="line">            <span class="keyword">int</span> num = random.nextInt();</span><br><span class="line">            System.out.println(<span class="string">"读取了第 "</span> + (i + <span class="number">1</span>) + <span class="string">"\t个数: "</span> + num);</span><br><span class="line">            bytes = ms.splitBigData(num);</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(<span class="string">""</span>);</span><br><span class="line">        ms.output(bytes);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 读取数据，并将对应数数据的 到对应的bit中，并返回byte数组</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> num 读取的数据</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> byte数组  dataBytes</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">byte</span>[] splitBigData(<span class="keyword">int</span> num) &#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">long</span> bitIndex = num + (<span class="number">1l</span> &lt;&lt; <span class="number">31</span>);         <span class="comment">//获取num数据对应bit数组（虚拟）的索引</span></span><br><span class="line">        <span class="keyword">int</span> index = (<span class="keyword">int</span>) (bitIndex / <span class="number">8</span>);         <span class="comment">//bit数组（虚拟）在byte数组中的索引</span></span><br><span class="line">        <span class="keyword">int</span> innerIndex = (<span class="keyword">int</span>) (bitIndex % <span class="number">8</span>);    <span class="comment">//bitIndex 在byte[]数组索引index 中的具体位置</span></span><br><span class="line"></span><br><span class="line">        System.out.println(<span class="string">"byte["</span> + index + <span class="string">"] 中的索引："</span> + innerIndex);</span><br><span class="line"></span><br><span class="line">        dataBytes[index] = (<span class="keyword">byte</span>) (dataBytes[index] | (<span class="number">1</span> &lt;&lt; innerIndex));</span><br><span class="line">        <span class="keyword">return</span> dataBytes;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 输出数组中的数据</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> bytes byte数组</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">output</span><span class="params">(<span class="keyword">byte</span>[] bytes)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; bytes.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">8</span>; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (!(((bytes[i]) &amp; (<span class="number">1</span> &lt;&lt; j)) == <span class="number">0</span>)) &#123;</span><br><span class="line">                    count++;</span><br><span class="line">                    <span class="keyword">int</span> number = (<span class="keyword">int</span>) ((((<span class="keyword">long</span>) i * <span class="number">8</span> + j) - (<span class="number">1l</span> &lt;&lt; <span class="number">31</span>)));</span><br><span class="line">                    System.out.println(<span class="string">"取出的第  "</span> + count + <span class="string">"\t个数: "</span> +  number);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="2、分治法"><a href="#2、分治法" class="headerlink" title="2、分治法"></a>2、分治法</h3><p>分治法目前看到的解决方案有<strong>哈希分桶（Hash Buckets）</strong>和<strong>归并排序</strong>两种方案。</p>
<p>哈希分桶的思想是先遍历一遍，按照hash分N桶（比如1000桶），映射到不同的文件中。这样平均每个文件就10MB，然后分别处理这1000个文件，找出没有重复的即可。一个相同的数字，绝对不会夸文件，<a href="https://maimai.cn/web/gossip_detail?src=app&amp;webid=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1IjozNDM5ODY0MiwiaWQiOjgzODU0NDR9.zf_21BO_wwAo0t1D8UdKAC9tKXv2TuphOhGnKtCq51E" target="_blank" rel="noopener">有hash做保证</a>。因为算法具体还不甚了解，这里先不做详细介绍。</p>
<p>归并排序的思想可以参考这篇文章：<a href="http://www.cnblogs.com/cnyao/archive/2009/11/09/interview7.html" target="_blank" rel="noopener">面试题之10亿正整数问题续–关于多通道排序的问题</a></p>
<hr>
<h2 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h2><ol>
<li><a href="http://blog.csdn.net/v_july_v/article/details/6451990" target="_blank" rel="noopener">程序员编程艺术：第十章、如何给10^7个数据量的磁盘文件排序</a></li>
<li><a href="http://www.cnblogs.com/cnyao/archive/2009/11/09/interview7.html" target="_blank" rel="noopener">面试题之10亿正整数问题续–关于多通道排序的问题</a></li>
<li><a href="http://yacare.iteye.com/blog/1969931" target="_blank" rel="noopener">利用位映射原理对大数据排重</a></li>
<li><a href="http://blog.csdn.net/v_july_v/article/details/6279498" target="_blank" rel="noopener">十道海量数据处理面试题与十个方法大总结</a></li>
<li><a href="http://www.cnblogs.com/moonandstar08/p/5236539.html" target="_blank" rel="noopener">海量数据处理之BitMap</a></li>
</ol>
<p><a href="javascript:;" target="_blank" rel="noopener">**</a></p>

        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    最后更新时间：<time datetime="2017-08-27T08:16:31.401Z" itemprop="dateUpdated">2017-08-27 16:16:31</time>
</span><br>


        
        原文链接：<a href="/2017/08/27/bitmap/" target="_blank" rel="external">https://lvshen9.gitee.io/2017/08/27/bitmap/</a>
        
    </div>
    
    <footer>
        <a href="https://lvshen9.gitee.io">
            <img src="/img/avatar.jpg" alt="我的技术小房间">
            我的技术小房间
        </a>
    </footer>
</blockquote>

        
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;" class="page-reward-btn waves-effect waves-circle waves-light">赏</a>
</div>



        <div class="post-footer">
            
	<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/bitmap/">bitmap</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/算法/">算法</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=https://lvshen9.gitee.io/2017/08/27/bitmap/&title=《【算法】10亿int型数，统计只出现一次的数》 — Lvshen's Blog&pic=https://lvshen9.gitee.io/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://lvshen9.gitee.io/2017/08/27/bitmap/&title=《【算法】10亿int型数，统计只出现一次的数》 — Lvshen's Blog&source=
本文来自 Itimetraveler’s Blog： 【算法】10亿int型数，统计只出现一次的数

题目10亿int整型数，以及一台可用内存为1GB的..." data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=https://lvshen9.gitee.io/2017/08/27/bitmap/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《【算法】10亿int型数，统计只出现一次的数》 — Lvshen's Blog&url=https://lvshen9.gitee.io/2017/08/27/bitmap/&via=https://lvshen9.gitee.io" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=https://lvshen9.gitee.io/2017/08/27/bitmap/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/2017/08/28/遗传算法的基本概念和Java实现/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">遗传算法的基本概念和Java实现</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/2017/08/27/sort/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">八大排序算法总结与java实现</h4>
      </a>
    </div>
  
</nav>



    











    <!-- Valine Comments -->
    <div class="comments vcomment" id="comments"></div>
    <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
    <script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script>
    <!-- Valine Comments script -->
    <script>
        var GUEST_INFO = ['nick','mail','link'];
        var guest_info = 'nick,mail,link'.split(',').filter(function(item){
          return GUEST_INFO.indexOf(item) > -1
        });
        new Valine({
            el: '#comments',
            notify: 'false' == 'true',
            verify: 'false' == 'true',
            appId: "dy9kXHwg5jQUlLryQmpjWRlM-gzGzoHsz",
            appKey: "P9Nh39Ol0JbMMiYqNGHEP3ml",
            avatar: "mm",
            placeholder: "Just go go",
            guest_info: guest_info.length == 0 ? GUEST_INFO : guest_info,
            pageSize: "10"
        })
    </script>
    <!-- Valine Comments end -->







</article>

<div id="reward" class="page-modal reward-lay">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <h3 class="reward-title">
        <i class="icon icon-quote-left"></i>
        谢谢大爷~
        <i class="icon icon-quote-right"></i>
    </h3>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="https://lvshen9.github.io/blog2/pay/weixin.jpg" alt="打赏二维码">
        </div>
        
        <label class="reward-toggle">
            <input id="rewardToggle" type="checkbox" class="reward-toggle-check"
                data-wechat="https://lvshen9.github.io/blog2/pay/weixin.jpg" data-alipay="https://lvshen9.github.io/blog2/pay/zhifu.jpg">
            <div class="reward-toggle-ctrol">
                <span class="reward-toggle-item wechat">微信</span>
                <span class="reward-toggle-label"></span>
                <span class="reward-toggle-item alipay">支付宝</span>
            </div>
        </label>
        
    </div>
</div>



</div>

        <footer class="footer">
    <div class="top">
        
<p>
    <span id="busuanzi_container_site_uv" style='display:none'>
        站点总访客数：<span id="busuanzi_value_site_uv"></span>
    </span>
    <span id="busuanzi_container_site_pv" style='display:none'>
        站点总访问量：<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


        <p>
            
            <span>博客内容遵循 <a rel="license" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">知识共享 署名 - 非商业性 - 相同方式共享 4.0 国际协议</a></span>
        </p>
    </div>
    <div class="bottom">
        <p><span>我的技术小房间 &copy; 2015 - 2020</span>
            <span>
                
                Power by <a href="http://hexo.io/" target="_blank">Hexo</a> Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
            </span>
        </p>
    </div>
</footer>

    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=https://lvshen9.gitee.io/2017/08/27/bitmap/&title=《【算法】10亿int型数，统计只出现一次的数》 — Lvshen's Blog&pic=https://lvshen9.gitee.io/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://lvshen9.gitee.io/2017/08/27/bitmap/&title=《【算法】10亿int型数，统计只出现一次的数》 — Lvshen's Blog&source=
本文来自 Itimetraveler’s Blog： 【算法】10亿int型数，统计只出现一次的数

题目10亿int整型数，以及一台可用内存为1GB的..." data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=https://lvshen9.gitee.io/2017/08/27/bitmap/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《【算法】10亿int型数，统计只出现一次的数》 — Lvshen's Blog&url=https://lvshen9.gitee.io/2017/08/27/bitmap/&via=https://lvshen9.gitee.io" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=https://lvshen9.gitee.io/2017/08/27/bitmap/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="//api.qrserver.com/v1/create-qr-code/?data=https://lvshen9.gitee.io/2017/08/27/bitmap/" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/', SHARE: true, REWARD: true };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>






<script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>



<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = '死鬼去哪里了！';
            clearTimeout(titleTime);
        } else {
            document.title = '(つェ⊂)咦!又好了!';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
